#include <iostream>
#include <stack>

using namespace std;

// 279 : perfect Square 无权有向图最短路径
// 时间复杂度: O(n)	空间复杂度: O(n)
class Solution {
public:
	// 返回多少个完全平方数
	int numSquares(int n) {
		if(n == 0) return 0;
		queue<pair<int, int>> q;// (第几个数字， 经历了几个节点)
		q.push(make_pair(n, 0));

		vector<bool> visited(n+1, false);
		visited[n] = true;

		while(!q.empty()){
			int num = q.front().first;			// 数字
			int step = q.front().second;
			q.pop();

			if(num == 0)
				return step;
			// 会将冗余数据推入数组
			for(int i = 0; num - i*i >= 0; i++){
				int a = num - i*i;
				if(!visited[a]){		// 如果该节点未被访问过，将其推入队列
					if(a == 0) return step + 1;
					q.push(make_pair(a, step + 1));
					visited[a] = true;	// 更新被访问状态
				}
			}
		}

		throw invalid_argument("No Solution.");
	}
};

int main(){}
